// https://leetcode.cn/problems/combination-sum-ii/

// https://leetcode.cn/problems/combination-sum-ii/

class Solution {
public:
        void dfs(vector<vector<int>>& res, vector<int>& tmp, vector<int>& candidates, int sum, int target, int start) {
        if (sum >= target) {
            if (sum == target)
                res.push_back(tmp);
            return;
        }
        for (int i = start; i < candidates.size(); ++i) {
            if (candidates[i] > target) continue; // 剪枝
            if (i > start && candidates[i] == candidates[i - 1]) continue; // 判断
            tmp.push_back(candidates[i]);
            sum += candidates[i];
            dfs(res, tmp, candidates, sum, target, i + 1); // 改成i+1
            tmp.pop_back();
            sum -= candidates[i];
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> tmp;
        sort(candidates.begin(), candidates.end());
        dfs(res, tmp, candidates, 0, target, 0);
        return res;
    }
};


class Solution {
public:
        void dfs(vector<vector<int>>& res, vector<int>& tmp, vector<int>& candidates, int sum, int target, int start, vector<bool>& visited) {
        if (sum >= target) {
            if (sum == target)
                res.push_back(tmp);
            return;
        }
        for (int i = start; i < candidates.size(); ++i) {
            if (visited[i] || (i > 0 && candidates[i] == candidates[i - 1] && !visited[i - 1])) continue;
            if (candidates[i] > target) continue; // 剪枝
            tmp.push_back(candidates[i]);
            sum += candidates[i];
            visited[i] = true;
            dfs(res, tmp, candidates, sum, target, i, visited);
            // 用了visited数组，传i或者i+1都行
            tmp.pop_back();
            sum -= candidates[i];
            visited[i] = false;
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> tmp;
        vector<bool> visited(candidates.size(), false);
        sort(candidates.begin(), candidates.end());
        dfs(res, tmp, candidates, 0, target, 0, visited);
        return res;
    }
};


